//
// Created by 麻再挺 on 2021/1/19.
//

#include "linear_list_impl.h"

/**
 * 初始化线性表
 * @param list 线性表
 * @return
 */
Status Linear_List_Init(LinearList *list) {
    // 构造一个空的线性表
    list->elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    // 如果list.elem值为0, 则代表分配成功
    if (!list->elem) {
        return OVERFLOW;
    }
    // 空表长度
    list->length = 0;
    // 初始存储容量
    list->list_size = LIST_INIT_SIZE;
    return OK;
}

/**
 * 插入线性表数据: 在第 i 个位置插入
 * @param list 线性表
 * @param i 位置
 * @param elem 数据类型
 * @return
 */
Status Linear_List_Insert(LinearList *list, int i, ElemType elem) {
    // 判断插入位置是否合法
    if (i < 0 || i > list->length + 1) return ERROR;
    // 当存储空间已满, 增加分配
    if (list->length >= list->list_size) {
        // 重新申请内存空间
        ElemType *new_base = (ElemType *) realloc(list->elem, (list->list_size + LIST_INCREMENT) * sizeof(ElemType));
        // 存储空间分配是否失败
        if (!new_base) {
            return OVERFLOW;
        }
        // 赋值
        list->elem = new_base;
        // 增加存储容量
        list->list_size += LIST_INCREMENT;
    }
    // 获取插入位置
    ElemType *q = &(list->elem[i]);
    // 临时插入位置
    ElemType *p;
    // 将线性表中数据后移
    for (p = &(list->elem[list->length - 1]); p >= q; p--) {
        *(p + 1) = *p;
    }
    // 赋值节点数值
    *q = elem;
    // 表长+1
    ++list->length;
    return OK;
}

/**
 * 添加数据, 在最后一个位置添加
 * @param list 列表
 * @param elem 数据
 * @return
 */
Status Linear_List_Push(LinearList *list, ElemType elem) {
    // 当存储空间已满, 增加分配
    if (list->length >= list->list_size) {
        // 重新申请内存空间
        ElemType *new_base = (ElemType *) realloc(list->elem, (list->list_size + LIST_INCREMENT) * sizeof(ElemType));
        // 存储空间分配是否失败
        if (!new_base) return OVERFLOW;
        // 赋值
        list->elem = new_base;
        // 增加存储容量
        list->list_size += LIST_INCREMENT;
    }
    // 获取插入位置
    ElemType *q = &(list->elem[list->length]);
    // 赋值节点数据
    *q = elem;
    // 表长+1
    ++list->length;
    return OK;
}

/**
 * 移除数据, 最后一位数据移除
 * @param list 线性表
 */
void Linear_List_Pop(LinearList *list) {
    // 表长-1
    --list->length;
}

/**
 * 删除线性表指定位置数据
 * @param list 线性表
 * @param i 位置
 * @return
 */
Status Linear_List_Delete(LinearList *list, int i) {
    // 判断插入位置是否合法
    if (i < 0 || i > list->length + 1) return ERROR;
    // 获取被删除元素的位置
    ElemType *p = &(list->elem[i]);
    // 获取表尾元素
    ElemType *q = list->elem + list->length - 1;
    // 被删除元素之后的数据左移
    for (++p; p <= q; ++p) *(p - 1) = *p;
    // 表长-1
    --list->length;
    return OK;
}

/**
 * 查询指定元素在线性表中的位置
 * @param list 列表
 * @param elem 元素
 * @param compare 比较函数
 * @return -1: 不存在; 非-1: 元素索引
 */
int Linear_List_Locate_Elem(LinearList *list, ElemType elem, Status(*compare)(ElemType, ElemType)) {
    // 设置索引的初始值
    int i = 0;
    // 设置初始值位置
    ElemType *p = &list->elem[0];
    // 查找
    while (i <= list->length && !(*compare)(*p++, elem)) i++;
    if (i <= list->length) {
        return i;
    } else {
        return -1;
    }
}

/**
 * 合并两个列表
 * @param list1 待合并列表1(元素依值递增)
 * @param list2 待合并列表2(元素依值递增)
 * @param list3 合并后列表3(元素依值递增)
 * @return
 */
Status Linear_List_Merge(LinearList *list1, LinearList *list2, LinearList *list3) {
    // 获取列表1与列表2首地址
    ElemType *pa = list1->elem, *pb = list2->elem;
    // 赋值合并后列表长度
    list3->list_size = list3->length = list1->length + list2->length;
    // 申请内存
    ElemType *pc = list3->elem = (ElemType *) malloc(list3->list_size * sizeof(ElemType));
    // 判断是否申请成功
    if (!pc) { return OVERFLOW; }
    // 计算第一个列表最后一个元素位置
    ElemType *pa_last = list1->elem + list1->length - 1;
    // 计算第二个列表最后一个元素位置
    ElemType *pb_last = list2->elem + list2->length - 1;
    // 合并
    while (pa <= pa_last && pb <= pb_last) {
        // 如果第一个列表中数据小于第二个列表中数据, 则赋值
        if (*pa <= *pb) {
            *pc++ = *pa++;
        } else {
            // 否则将第二个列表中数据赋值
            *pc++ = *pb++;
        }
    }
    // 插入第一个列表的剩余元素
    while (pa <= pa_last) *pc++ = *pa++;
    // 插入第二个列表的剩余元素
    while (pb <= pb_last) *pc++ = *pb++;
    return OK;
}

/**
 * 判断列表是否为空
 * @param list 列表
 * @return TRUE: 空; FALSE: 不为空
 */
Status Linear_List_Empty(LinearList *list) {
    if (list->length == 0) {
        return TRUE;
    } else {
        return FALSE;
    }
}


/**
 * 列表长度
 * @param list 列表
 * @return 具体数值
 */
int Linear_List_Length(LinearList *list) {
    return list->length;
}


/**
 * 根据索引获取元素
 * @param list 列表
 * @param i 索引
 * @param elem 元素
 */
void Linear_List_Get_Elem(LinearList *list, int i, ElemType *elem) {
    *elem = list->elem[i];
}

/**
 * 打印列表数据
 * 注: 此处先使用int强转, 因为现在ElemType是int
 * @param list 列表
 */
void Linear_List_Print(LinearList *list) {
    for (int i = 0; i < list->length; ++i) {
        printf("%d", (int) *(list->elem + i));
        if (i < list->length - 1) {
            printf(", ");
        }
    }
    printf("\n");
}